import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;


public class IslaTurbia {
	
	private Casillero[][] tableroDeFloodFill;
	private int marea;
	private List<Valla> listaValla = null;
	private int contInundaciones = 0;
	private int cantDeCasillerosSecos = 0;
	
	private int maxY = 0;
	private int maxX = 0;
	private int minX = Integer.MAX_VALUE;
	private int minY = Integer.MAX_VALUE;
	
	private int altoMatriz = 0; 
	private int largoMatriz = 0;
	
	public IslaTurbia(Integer marea, List<Valla> listaValla) {
		this.listaValla = listaValla;
		this.marea = marea;
	}
	
	private void floodFill(Integer x, Integer y, String dedondevengo) {
		if( tableroDeFloodFill[x][y].inundado ){
			return;
		}
		Queue<DireccionesDelTablero> queue = new ConcurrentLinkedQueue<DireccionesDelTablero>();
		
		queue.add(new DireccionesDelTablero(x,y));
		while (!queue.isEmpty()) {
			DireccionesDelTablero cas = queue.poll();
			
			if(cas.x < 0 || cas.y < 0 || cas.y > altoMatriz || cas.x > largoMatriz || tableroDeFloodFill[cas.x][cas.y].inundado ){
				continue;
			}
			
			tableroDeFloodFill[cas.x][cas.y].inundado = true;
			contInundaciones++;
			
			if(tableroDeFloodFill[cas.x][cas.y].puedoNorte(marea)){
				queue.add(new DireccionesDelTablero(cas.x,cas.y -1));
			}
			
			if(tableroDeFloodFill[cas.x][cas.y].puedoSur(marea)){
				queue.add(new DireccionesDelTablero(cas.x,cas.y + 1));
			}
			
			if(tableroDeFloodFill[cas.x][cas.y].puedoOeste(marea)){
				queue.add(new DireccionesDelTablero(cas.x -1,cas.y));
			}
			
			if(tableroDeFloodFill[cas.x][cas.y].puedoEste(marea)){
				queue.add(new DireccionesDelTablero(cas.x + 1,cas.y));
			}
		}
	}

	/**************************************************Rellenar Matriz de Casilleros**********************************************************/
	private void rellenarMatrizDeIncidencia(List<Valla> listaValla) {

		//Por cada valla, rellena desde donde arranca y hasta donde termina los casilleros de al lado
		for (Valla valla : listaValla) {
			if (valla.orientacion.equals("|")){
				fillVertical(valla);
			} else {
				fillHorizontal(valla);
			}
//			imprimirMatriz();
		}
	}

	private void fillHorizontal(Valla valla) {
		valla.x = (valla.x - minX) + 1;
		valla.y = (valla.y - minY) + 1;
		
			comunHorizontal(valla);
	}

	private void comunHorizontal(Valla valla) {
		for (int i = 0; i < valla.largo; i++) {
			tableroDeFloodFill [ valla.x + i ] [ altoMatriz - (valla.y - 1) ].norte = valla.altura;
			tableroDeFloodFill [ valla.x + i ] [ altoMatriz -     valla.y   ].sur = valla.altura;
		}
	}

	private void fillVertical(Valla valla) {
		valla.x = (valla.x - minX) + 1;
		valla.y = (valla.y - minY) + 1;
		
			comunVertical(valla);
	}

	private void comunVertical(Valla valla) {
		for (int i = 0; i < valla.largo; i++) {
			tableroDeFloodFill [ valla.x -1 ] [ altoMatriz - (valla.y + i) ].este= valla.altura;
			tableroDeFloodFill [ valla.x    ] [ altoMatriz - (valla.y + i) ].oeste = valla.altura;
		}
	}
	
	/**************************************************Fin Rellenar Matriz de Casilleros**********************************************************/

	private void crearGrafoConLasParedes(List<Valla> listaValla) {		
		buscarMaxMin(listaValla);
		
		int largoTablero = maxX - minX;
		int altoTablero = maxY - minY;
		
		tableroDeFloodFill = new Casillero[largoTablero + 2][altoTablero + 2];
		
		altoMatriz = altoTablero + 1;
		largoMatriz = largoTablero + 1;
		
		cantDeCasillerosSecos = (largoTablero + 2) * (altoTablero + 2);
		
		for (int i = 0; i < largoTablero + 2; i++) {
			for (int j = 0; j < altoTablero + 2; j++) {
				tableroDeFloodFill[i][j] = new Casillero();				
			}
		}
	}

	private void buscarMaxMin(List<Valla> listaValla) {
		for (Valla valla : listaValla) {
			
			
			if (minX > valla.x){
				minX = valla.x;
			}
			
			if (minY > valla.y){
				minY = valla.y;
			}
			
			
			if(valla.orientacion.equals("|")){
				if (maxY < valla.y + valla.largo){
					maxY = valla.y + valla.largo;
				}
				
				if (maxX < valla.x){
					maxX = valla.x;
				}				
			} else {
				if (maxY < valla.y){
					maxY = valla.y;
				}

				if (maxX < valla.x + valla.largo){
					maxX = valla.x + valla.largo;
				}				
			}
		}
	}

	public Integer operacionSalvatajeDeDroga() {

		contInundaciones = 0;
		
		crearGrafoConLasParedes(listaValla);
			
		rellenarMatrizDeIncidencia(listaValla);
		
		floodFill(0, 0, ". ");
		return cantDeCasillerosSecos - contInundaciones;
	}

}
